1. Field of the Invention
The present invention generally relates to memory vacancy management apparatuses and line interface units, and more particularly to a memory vacancy management apparatus for managing vacant addresses of a memory and to a line interface unit which uses such a memory vacancy management apparatus.
Usually, memories are used in various kinds of apparatuses and equipments used in the field of communication, typified by switching systems, transmission units and terminal equipments. Such memories have various structures and functions. For example, a RAM coupled to a microprocessor bus may be used for a control unit or signal control. In addition, a memory may be provided in a channel system to process the communication data itself, such as a First-In-First-Out (FIFO) which absorbs a phase error of a clock and an elastic memory.
2. Description of the Related Art
Amongst the above described memories, there is a memory which is provided with a function of searching vacant addresses which are not in use.
FIG. 1 is a system block diagram showing an example of a conventional memory having the vacant address searching function. The memory includes a memory cell part (MCELL) 1, a vacant address management table (VTBL) 2, an access controller (ACTL) 3, and a vacant address searcher (VSCH) 4 which are connected as shown in FIG. 1.
The memory cell part 1 stores external data written therein. The vacant address management table 2 has the same address structure as the memory cell part 1, and contains information which indicates whether or not data are stored at corresponding addresses of the memory cell part 1, that is, whether or not the corresponding addresses of the memory cell part 1 are xe2x80x9cin usexe2x80x9d or xe2x80x9cvacantxe2x80x9d. The access controller 3 controls access, that is, read and write, with respect to the memory cell part 1. In addition, the access controller 3 controls updating of the contents of the vacant address management table 2. The vacant address searcher 4 searches for a next vacant address to which the writing is possible, based on the contents of the vacant address management table 2. The access controller 3 receives a signal ACADR which indicates the address, a write data WDATA, a write request WREQ, and a read request RREQ, and outputs read data RDATA.
FIG. 2 is a flow chart for explaining the operation of the conventional memory shown in FIG. 1. In FIG. 2, a step initializes the vacant address management table 2 and the memory cell part 1. When the initializing of the vacant address management table 2 and the memory cell part 1 ends, a step S2 decides whether or not an access is made from outside the memory. If the decision result in the step S2 is YES, a step S3 decides whether the access is a read or a write.
If the access is the write, a step S4 decides whether or not the vacant address searcher 4 outputs a signal FULL which indicates that the memory cell part 1 is full. If the decision result in the step S4 is NO, a step S5 writes the write data WDATA into the memory cell part 1 at an address corresponding to a vacant address VADR output from the vacant address searcher 4, and at the same time, sets xe2x80x9cin usexe2x80x9d in the vacant address management table 2 at the corresponding address.
On the other hand, if the access is the read in the step S3, a step S6 decides whether or not an address ACADR of the memory cell part 1 is in use. If the decision result in the step S6 is YES, a step S7 reads the data written at the address ACADR, and sets xe2x80x9cvacantxe2x80x9d in the vacant address management table 2 at an address corresponding to the address ACADR.
Next, in a step S8, the vacant address searcher 4 carries out a vacancy search process by making a reference to the vacant address management table 2. A step S9 decides whether or not a vacant address is found. If the decision result in the step S9 is YES, a step S10 sets the vacant address found as the vacant address VADR. On the other hand, if the decision result in the step S9 is NO, a step S11 outputs the signal FULL which indicates that there is no vacant address in the vacant address management table 2.
According to this conventional memory, the vacant address searcher 4 constantly searches for the vacant address within the memory cell part 1, and the vacant address found as a result of the search is notified to the access controller 3. Here, the vacant address refers to the address where no valid data is written in the memory cell part 1 from outside the memory. Accordingly, when an external circuit which uses the memory needs to buffer the data into the memory, it is first necessary to check whether or not the signal FULL is output from the memory. If no signal FULL is output from the memory, the data to be buffered is input to the memory as the write data WDATA, while making the write request WREQ to the memory active.
By the operation described above, the write data WDATA which is to be buffered in the memory is stored at the address of the memory cell part 1 indicated by the vacant address VADR. Hence, the external circuit which uses the memory does not have to be aware of which addresses are vacant. After the write data WDATA is written at the address which is indicated by the vacant address VADR, the address is no longer xe2x80x9cvacantxe2x80x9d, and thus, at the same time as writing the write data WDATA into the memory cell part 1, the access controller 3 writes a flag which indicates xe2x80x9cin usexe2x80x9d at the corresponding address of the vacant address management table 2. Furthermore, a trigger for starting the search is issued from the access controller 3 to the vacant address searcher 4 in order to search for the new vacant address VADR.
On the other hand, when the access to the memory is the read, the external circuit which uses the memory inputs the signal ACADR to the access controller 3, and then makes the read request RREQ active. As a result, the read data RDATA indicates the content of the memory cell part 1 at the address specified by the signal ACADR. In addition, since the read address of the memory cell part 1 is no longer xe2x80x9cin usexe2x80x9d, the access controller 3 simultaneously writes the flag which indicates xe2x80x9cvacantxe2x80x9d at the corresponding address of the vacant address management table 2. By updating the vacant address management table 2, the vacancy state of the memory cell part 1 also changes, but it is unnecessary to trigger the start of the search in this case, because it remains unchanged that the vacant address VADR already found by the vacant address searcher 4 is xe2x80x9cvacantxe2x80x9d.
In a case where the signal FULL is output before the read is carried out with respect to the memory, the vacant address VADR does not indicate a valid vacant address, and it is necessary in this case to trigger the start of the search. In this case, it is clear that only the address just read is vacant, there is no need to search for the vacant address, and it is sufficient to simply copy the signal ACADR as the vacant address VADR.
Conventionally, the memory having the vacant address search function is generally realized by a software approach, that is, the entire memory or a part excluding a memory part corresponding to the memory cell part 1 is realized by software. In this case, a microprocessor or the like is used to carry out the vacant address search operation of the vacant address searcher 4. FIG. 3 is a diagram showing the construction of the memory using a microprocessor. In FIG. 3, those parts which are the same as those corresponding parts in FIG. 1 are designated by the same reference numerals. FIG. 3 shows a case where a microprocessor 10 is coupled to another circuit via a processor bus 13.
A RAM 11 which forms the memory includes the memory cell part (main buffer part) 1, the vacant address management table 2, the access controller (access control program) 3, and the vacant address searcher (VTBL search program) 4. An input/output (I/O) port 12 is coupled to the processor bus 13, and forms an interface with respect to an external apparatus which uses the memory.
In order to realize the various functions of the RAM 11 by the microprocessor 10, the vacant address management table 2 which is used to search for the vacant address is provided within the RAM 11 which is under control of the microprocessor 10. The operation of the memory is realized by a software which makes a reference to and updates the vacant address management table 2. The process carried out by the memory is the same as that shown in FIG. 2, even when the software is used to realize the various functions of the memory.
But recently, particularly in the field of communication, there are demands to realize extremely high processing speeds in apparatuses which employ techniques such as the Asynchronous Transfer Mode (ATM) switching technique and the optical transmission technique. In a case where the data to be stored in the above described memory us a channel system data, it is necessary to realize a processing speed greater than or equal to a throughput of the line. For example, in a OC-3c interface which is a Synchronous Optical NETwork (SONET) line, the throughput is 155.53 Mbps, and thus, it is becoming impossible to carry out a software processing by the microprocessor 10 unless a parallel processing is made with 32 bits, 64 bits or a larger number of bits. However, it is undesirable to increase the number of bits that are processed in parallel, since it would increase the hardware scale of the apparatus.
When considering constructing the memory purely by hardware in view of the above, a method of searching the vacant address in the vacant address management table 2 becomes a problem.
FIG. 4 is a system block diagram showing the construction of the conventional vacant address searcher 4. The vacant address searcher 4 shown in FIG. 4 includes an address generating counter (SCNT) 20 is capable of generating addresses to specify the entire vacant address management table 2, and a controller which reads and writes with respect to the vacant address management table 2 based on an output of the counter 20. The counter 20 is started by an external trigger, and generates the address starting from a least significant address towards a most significant address or vice versa. Of course, the counter 20 may generate the address starting from an intermediate address. An address selector 21 selects an external address ACADR or the output address of the counter 20 depending on an output of a selector controller 22, and supplies the selected address to the vacant address management table 2.
The controller reads the vacant address management table 2 based on the output address of the counter 20, and the counter 20 stops the count when the vacant address is read from the vacant address management table 2. A vacancy detector 23 detects the vacant address, and stores the vacant address in a vacant address storage 24. The vacant address storage 24 outputs the vacant address VADR stored therein. A write data creating part 25 creates a write data which indicates whether or not the address is vacant, and supplies the write data to the vacant address management table 2. A read/write controller 26 controls the read and write with respect to the vacant address management table 2.
FIG. 5 is a timing chart for explaining the operation of the conventional vacant address searcher 4 shown in FIG. 4. FIG. 5(a) shows a count start signal CNTST, FIG. 5(b) shows an output address CADR of the counter 20, FIG. 5(c) shows an output address SADR of the address selector 21, FIG. 5(d) shows an output RFLG of the vacant address management table 2, FIG. 5(e) shows an output VDET of the vacancy detector 23 indicating whether or not the address is vacant, and FIG. 5(f) shows an output address VADR of the vacant address searcher 4 obtained from the vacant address storage 24.
When the count start signal CNTST is generated, the address selector 21 selects the output address CADR of the counter 20. When the output address CADR of the counter 20 is successively updated from 0, a reference is made to the contents at the corresponding addresses of the vacant address management table 2. In this state, the addresses 0 through 2 are in use. When the output address CADR of the counter 20 becomes 3, the corresponding address and subsequent addresses of the vacant address management table 2 indicate vacancy. The output VDET of the vacancy detector 23 indicating whether or not the address is vacant is supplied to the vacant address storage 24, and the output vacant address VADR from the vacant address storage 24 is supplied to the access controller 3.
Actually, the vacant addresses are searched successively, and for this reason, it takes time to find the vacant address as the number of vacant addresses becomes small. The time required to find the vacant address becomes larger as the size of the vacant address management table 2 becomes larger. As a result, the original purpose of realizing the memory purely by hardware, that is, to improve the processing speed which cannot be greatly improved from the software approach, cannot be achieved in a satisfactory manner. In other words, it is difficult to bring out the advantageous effects of realizing the memory purely by hardware.
Accordingly, it is a general object of the present invention to provide a novel and useful memory vacancy management apparatus and line interface unit, in which the problems described above are eliminated.
Another and more specific object of the present invention is to provide a memory vacancy management apparatus and line interface unit, which can positively find a vacant address at a high speed.
Still another object of the present invention is to provide a memory vacancy management apparatus for managing vacant addresses of a memory which is capable of storing various information, comprising a vacant address management table having a number of addresses identical to a number of addresses of the memory, and storing vacancy information indicating whether or not the addresses of the memory are vacant, wherein the vacancy information with respect to an address of the memory having an arbitrary address value is stored at an address of the vacant address management table having the same arbitrary address value. According to the memory vacancy management apparatus of the present invention, it is possible to recognize a vacant region of the memory and to positively find the vacant address at a high speed.
A further object of the present invention is to provide a line interface unit for exchanging ATM cells between up and down lines and an ATM switch in an ATM switching system, comprising OAM cell creating means for creating an OAM cell for one of the up and down lines responsive to a detection of an OAM cell from the other of the up and down lines or responsive to an external request, a memory storing an OAM cell data queue of created OAM cells which is shared by a plurality of lines, a shared buffer management table managing a sending sequence of the OAM cell data stored in the memory for each line, and OAM cell inserting means for inserting the created OAM cell on the one of the up and down lines responsive to a detection of an idle cell on the one of the up and down lines, by making a reference to the shared buffer management table, where the shared buffer management table has a number of addresses identical to a number of addresses of the memory and stores vacancy information indicating whether or not the addresses of the memory are vacant, and the vacancy information with respect to an address of the memory having an arbitrary address value is stored at an address of the shared buffer management table having the same arbitrary address value. According to the line interface unit of the present invention, it is possible to recognize a vacant region of the memory and to positively find the vacant address at a high speed, so that the processing speed of the line interface unit can be improved.
Other objects and further features of the present invention will be apparent from the following detailed description when read in conjunction with the accompanying drawings.